#pragma once
#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
void dijkstra(int f, vector<vector<ll>>& d, vector<char>& hs, vector<vector<pair<ll, ll>>>& map) {
	auto cmp = [&](auto& a, auto& b) {return make_pair(d[a.first][a.second], a) < make_pair(d[b.first][b.second], b); };
	set<pair<ll, ll>, decltype(cmp)> st(cmp);
	st.insert({ f,0 });
	while (!st.empty()) {
		pair<ll, ll> u = *st.begin(); st.erase(st.begin());
		bool horse = u.second || hs[u.first];
		for (auto v : map[u.first]) {
			ll x = (horse ? v.second / 2 : v.second);
			if (d[v.first][horse] > d[u.first][u.second] + x) {
				st.erase({ v.first,horse });
				d[v.first][horse] = d[u.first][u.second] + x;
				st.insert({ v.first,horse });
			}
		}
	}
}